<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>哈希表实现</title>
	</head>
	<body>
	</body>
</html>
<script type="text/javascript">
	// 封装哈希表类
	
	function HashTable(){
		// 属性
		this.storage = [] //
		this.count = 0; //当前已经存放了多少元素
		// loadFactore  > 0.75 需要对数组进行扩容  ，性能变低
		// loadFactore  《 0.25 需要对数组进行减容 
		this.limit=7 //长度，限制为质数
		
		// 方法
		HashTable.prototype.hashFunc=function(str,size){
			// 1.定义hacshCode变量
			var hashCode = 0;
			
			// 2.霍纳算法，来计算hashCode的值
			// cats-> Unicode编码
			for (var i =0;i< str.length;i++) {
				 hashCode =  37*hashCode +	str.charAt(i)
			}
			
			// 3.取余操作
			var  index = hashCode % size
			 return index
		}
		// 再哈希
		HashTable.prototype.hashFuncTwo = function(key){
			return this.limit - (key & this.limit)
		} 
		// 插入&修改操作
		HashTable.prototype.put=function(key,value){
				// 1.根据key获取Index
				var  index = this.hashFunc(key,this.limit)
				
				// 2.根据index取出的对应的bucket
				var bucket = this.storage[index]
				
				// 3.判断是否为空
				if(bucket == null){
					bucket=[]
					this.storage[index] = bucket
				}
				
				// 4.判断是否修改数据
				for (var i = 0; i < bucket.length; i++) {
					 var tuple= bucket[i]
					 
					 if(tuple[0] ==key){
						 tuple[1]=value
						 return 
					 }
				}
				// 5.进行添加操作
				bucket.push([key,value])
				this.count+=1
				
				// 6.判断是否需要扩容操作
				if(this.count > this.limit*0.75){
					var prime = this.getPrime(this.limit*2)
					this.resize(prime)
				}
		}
		// 获取元素
		HashTable.prototype.get=function(key){
			// 1.根据key获取Index
			var  index = this.hashFunc(key,this.limit)
			
			// 2.根据index取出的对应的bucket
			var bucket = this.storage[index]
			// 3.判断是否为空
			if(bucket == null){
				return null
			}
			
			// 4.有Bucket，那么进行线性查找
			for (var i = 0; i < bucket.length; i++) {
				var tuple = bucket[i]
				if(tuple[0]==key){
					return tuple[1]
				}
			}
			// 5.依然没有找到
			return null
		}
		
		// 删除操作
		HashTable.prototype.remove=function(key){
			// 1.根据key获取Index
			var  index = this.hashFunc(key,this.limit)
			
			// 2.根据index取出的对应的bucket
			var bucket = this.storage[index]
			
			// 3.判断是否为空
			if(bucket == null){
				return null
			}
			// 4.有Bucket，那么进行线性查找
			for (var i = 0; i < bucket.length; i++) {
				var tuple = bucket[i]
				if(tuple[0]==key){
					 bucket.splice(i,1)
					 this.count--
					// 缩小容量
					if(this.limit > 7&&this.count < this.limit*0.25){
						 var prime = this.getPrime(Math.floor(this.limit/2))
						this.resize(prime)
					}
					return tuple[1]
				}
			}
			
			// 5.依然没有找到
			return null
			
		}
		// 其他方法
		// 判断哈希表是否为null
		HashTable.prototype.isEmpty=function(){
			return this.count==0		
		}
		
		// 获取哈希表的个数
		HashTable.prototype.size=function(){
			return this.count		
		}
		
		//   哈希表的扩容/减容
		HashTable.prototype.resize = function(newLimit){
			// 1.保存旧的数组内容
			 var oldStorage = this.storage
			// 2.重置所有的属性
			this.storage=[]
			this.count=0
			this.limit=newLimit
			
			// 3.遍历oldStorage中所有的bucket
				for (var i = 0 ;i< oldStorage.length;i++) {
					// 3.1取出对应的bucket
					var bucket = oldStorage[i]
					
					// 3.2判断bucket是否为空
					 if(bucket ==null){
						 continue
					 }
					 // 3.3 bucket中有数据，那么取出数据，重新输入
					 for (var j=0;j<bucket.length;j++) {
					 	var tuple=bucket[j]
						this.put(tuple[0],tuple[1])
					 }
				
				}
		}
		
		// 判断某个数字是否是质数
		HashTable.prototype.isPrime = function(num){
			// 1.获取Num的平方根
			var temp = parseInt(Math.sqrt(num))
			
			// 2.循环判断
			for(var i=2;i<=temp;i++){
				if(num % i == 0){
					return false
				}
			}
			return true
		}
		// 获取质数
		HashTable.prototype.getPrime = function(num){
			// 
			while(!this.isPrime(num)){
				num++
			}
			return num
		}
		HashTable.prototype.getStorage=function(){
			return this.storage
		}
			   
	}
	
	// 测试
	
	// 1.创建哈希表
	var hashT = new HashTable()
	
	// 2.插入数据
	hashT.put('abc','123')
	hashT.put('cbd','456')
	hashT.put('abc','789')
	hashT.put('efg','901')
	console.log(hashT.getStorage())

	// 3.获取数据
	// alert(hashT.get('abc'))
	
	// 4.修改
	
	// 5.删除
	// hashT.remove('cbd')
	// alert(hashT.get('cbd'))
</script>
